//Li M, Wang J, Zheng L, Wu H, Cheng P, Chen L, Lin X. Privacy-Preserving Batch-based Task Assignment in Spatial Crowdsourcing with Untrusted Server[M]. arXiv, 2021.
//文献复现代码
#pragma once
#include<iostream>
#include <cmath>

#include "EK.h"

using namespace std;

struct node_oscore
{
    double oscore;
    pair<int,int>p1,p2;
    int index1,index2;

    node_oscore(double oscore, pair<int,int> p1,pair<int,int> p2,int index1,int index2):
        oscore(oscore), p1(p1), p2(p2), index1(index1), index2(index2){}
    //定义弹出时从小到大排序    
    bool operator<(const node_oscore& o) const {
		return o.oscore < oscore;
	}
};

vector<node_oscore> h;//堆的创建

void printHeap(vector<node_oscore> &v){
    for(vector<node_oscore>::iterator it= v.begin();it!=v.end();++it){
        auto ver = *it;
        printf("%.6lf\t",ver.oscore);
    }
    cout<<"\n"<<endl;
}


/**
 * @brief 计算两个匹配对之间的分数
 * 
 * @param worker1 
 * @param worker2 
 * @param task1 
 * @param task2 
 * @return double 
 */
double calOscore(pair<double,double>& worker1,pair<double,double>& worker2,pair<double,double>& task1,pair<double,double>& task2){
    double workerDistance = sqrt((worker1.first-worker2.first)*(worker1.first-worker2.first)+(worker1.second-worker2.second)*(worker1.second-worker2.second));
    double taskDistance = sqrt((task1.first-task2.first)*(task1.first-task2.first)+(task1.second-task2.second)*(task1.second-task2.second));
    
    // vector<vector<double>> X(4,vector<double>(2,0));
    // X[0][0] = worker1.first;
    // X[0][1] = worker1.second;

    // X[1][0] = worker2.first;
    // X[1][1] = worker2.second;

    // X[2][0] = task1.first;
    // X[2][1] = task1.second;

    // X[3][0] = task2.first;
    // X[3][1] = task2.second;

    double mdist = MahalanobisDistance2(worker1,worker2,task1,task2);
    if(mdist !=-1) {
        return mdist;
    }
    
    return workerDistance+taskDistance;
}

void Ddivision(int&k,vector<vector<pair<int,int>>>&D){
    // calSMatrix();//计算方差矩阵
    h.clear();
    make_heap(h.begin(),h.end());
    pair<int,int>p1,p2;
    int MSize = M0.size();
    double tempOScore;
    // int workerNum = perturbWorkers.size();
    vector<bool> used(MSize,false);
    for (int i=0;i<MSize;i++){
        p1 = M0[i];
        used[i]=false;
        for(int j=0;j<MSize;j++){
            p2 = M0[j];
            if (p1.first!=p2.first){
                tempOScore = calOscore(perturbWorkers[p1.first].loc,perturbWorkers[p2.first].loc,perturbTasks[p1.second].loc,perturbTasks[p2.second].loc);
                h.push_back(node_oscore(tempOScore,p1,p2,i,j));
                push_heap(h.begin (),h.end());
            }
        }
    }
    int d;
    if (MSize%k==0)
        d = MSize/k;
    else
        d = MSize/k+1;
    // cout<<"d:"<<d<<endl;
    vector<pair<int,int>> g;
    int Dsize,gsize,hsize=1;//hsize=1是为了过掉第一次判断hsize==0
    pair<int,int>p;
    for(int i=0;i<d;i++){
        vector<pair<int,int>>().swap(g);
        // g.clear();
        gsize = g.size();
        Dsize = D.size();
        while(gsize<k){
            if(Dsize==d-1 || hsize==0){//最后的一个分配
                while(true){
                    hsize = h.size();
                    if(hsize==0)
                        break;
                    pop_heap(h.begin(),h.end());
                    auto node = h.back();
                    p1 = node.p1;
                    p2 = node.p2;
                    h.pop_back();//弹出删除
                    // cout<<"p1:"<<used[p1.first]<<"\tp2:"<<used[p2.first]<<endl;
                    // cout<<node.oscore<<endl;
                    if(used[node.index1]==false && used[node.index2]==false){
                        used[node.index1]=true;
                        used[node.index2]=true;
                        g.push_back(p1);
                        g.push_back(p2);
                        // break;
                    }
                }

                // cout<<"good1:"<<g.size()<<endl;
                for(int i=0;i<MSize;i++){
                
                    p =M0[i];
                    if(used[i]==false){
                        used[i]=true;
                        g.push_back(p);
                        // break;
                    }
                }
                // cout<<"good2:"<<g.size()<<endl;
                // if(gsize == MSize%k) break;
                // while (true)
                // {
                //     int pIndex = rand()%(MSize+1);
                //     // cout<<pIndex<<":"<<used[pIndex]<<endl;
                //     p =M0[pIndex];
                //     if(used[pIndex]==false){
                //         used[pIndex]=true;
                //         g.push_back(p);
                //         break;
                //     }
                // }
                
                break;
            }else{
                while(true){
                    hsize = h.size();
                    if(hsize==0)
                        break;
                    pop_heap(h.begin(),h.end());
                    auto node = h.back();
                    p1 = node.p1;
                    p2 = node.p2;
                    h.pop_back();//弹出删除
                    // cout<<"p1:"<<used[p1.first]<<"\tp2:"<<used[p2.first]<<endl;
                    // cout<<node.oscore<<endl;
                    if(used[node.index1]==false && used[node.index2]==false){
                        used[node.index1]=true;
                        used[node.index2]=true;
                        g.push_back(p1);
                        g.push_back(p2);
                        break;
                    }
                    // if(used[p1.first]==false){
                    //     used[p1.first]=true;
                    //     g.push_back(p1);
                    //     break;
                    // }
                    // if(used[p2.first]==false){
                    //     used[p2.first]=true;
                    //     g.push_back(p2);
                    //     break;
                    // }
                }
            }
                        
            gsize = g.size();
        }        
        D.push_back(g);
    }
    // if(count(used.begin(),used.end(),false)==1){
    //     cout<<"ggg"<<endl;
    // }
    // cout<<D[D.size()-3].size()<<endl;
    // cout<<D[D.size()-2].size()<<endl;
    // cout<<D.back().size()<<endl;
}
    
int HEprotocol(vector<vector<pair<int,int>>>&D,vector<int>&failWorkers,vector<int>&failTasks,vector<pair<int,int>>&Mg){
    //𝑘-HE protocol
    int successNum=0;
    vector<pair<int,int>>g;
    int Dsize,gsize;
    Dsize = D.size();
    vector<int>ww,tt;
    for (int i=0;i<Dsize;i++){
        g = D[i];
        gsize = g.size();     
        for (int j = 0; j < gsize; j++)
        {
            // if(count(ww.begin(),ww.end(),g[i].first)==0)
                ww.push_back(g[j].first);
            // else
                // cout<<"wrepeat"<<endl;
            // if(count(tt.begin(),tt.end(),g[i].second)==0)
                tt.push_back(g[j].second);
            // else
                // cout<<"trepeat"<<endl;
        }
        successNum += g_M(gsize,g,Mg,failWorkers,failTasks);             
    }
    // cout<<"ww:"<<ww.size()<<endl;
    // cout<<"tt:"<<tt.size()<<endl;
    // cout<<"success:"<<successNum<<endl;
    return successNum;
}
int KS_main(){
    // Greedy-Grouping
    vector<int> failWorkers,failTasks;
    vector<vector<pair<int,int>>> D;
    vector<pair<int,int>> Mg;
    int totalSuccess=0;
    for (int i=0;i<lamda;i++){
        D.clear();
        Ddivision(k,D);
        totalSuccess+=HEprotocol(D,failWorkers,failTasks,Mg);
        // cout<<"Mgsize:"<<Mg.size()<<endl;
        // if(failWorkers.size()!=failTasks.size())
        // cout<<"fail1:"<<failWorkers.size()<<" "<<failTasks.size()<<endl;
        // cout<<oblivious_M(failWorkers,failTasks)<<endl;
        oblivious_M(failWorkers,failTasks);
        // cout<<"fail2:"<<failWorkers.size()<<" "<<failTasks.size()<<endl;
    }
    // cout<<totalSuccess<<endl;
    // cout<<Mg.size()<<endl;
    /**
    //𝑘-HE protocol 
    vector<pair<int,int>>g;
    vector<int> failWorkers,failTasks;
    vector<pair<int,int>> Mg;
    int Dsize,gsize;
    Dsize = D.size();
    int ttt=0;
    for (int i=0;i<Dsize;i++){
        g = D[i];
        gsize = g.size();
        vector<pair<int,int>>().swap(Mg);

        int sss = g_M(gsize,g,Mg,failWorkers,failTasks);
        int mgsize = Mg.size();
        ttt +=sss;
        pair<int,int>oldP,newP;
        bool workerMatch=false,taskMatch=false;
        int nomw=0,nomt=0;
        for (int i = 0; i < gsize; i++)
        {
            oldP = g[i];
            workerMatch=false;
            taskMatch=false;
            for (int j=0;j<mgsize;j++){
                newP = Mg[j];
                if(oldP.first == newP.first){
                    workerMatch = true;
                }
                if(oldP.second == newP.second){
                    taskMatch = true;
                    // break; 
                }
            }
            if(!workerMatch){
                nomw++;
            }
            if (!taskMatch){
                nomt++;
                // cout<<"t:"<<oldP.second<<endl;
            }

        }
        // if(gsize-mgsize != nomt){
        //     cout<<"gsize:"<<gsize<<endl;
        //     cout<<"nw:"<<nomw<<"\t nt:"<<nomt<<endl;
        //     cout<<"ss:"<<sss<<endl;
        //     cout<<"success:"<<Mg.size()<<endl;
        //     for(int i=0;i<gsize;i++){
        //         // cout<<"("<<g[i].first<<","<<g[i].second<<")";
        //         printf("w %.10lf %.10lf 500 \nt %.11lf %.11lf \n",workerLists[g[i].first].loc.first,workerLists[g[i].first].loc.second,taskLists[g[i].second].loc.first,taskLists[g[i].second].loc.second);
        //     }
        //     // cout<<endl;
        //     for(int i=0;i<mgsize;i++){
        //         cout<<"("<<Mg[i].first<<","<<Mg[i].second<<")";
        //     }
        //     // cout<<endl;
        // }
        // cout<<endl;

        if(nomw!=nomt){
            cout<<"gsize:"<<gsize<<endl;
            cout<<"nw:"<<nomw<<"\t nt:"<<nomt<<endl;
            // cout<<"nw:"<<nomw<<endl;
            cout<<"success:"<<Mg.size()<<endl;
        }
        
    }
    cout<<ttt<<endl;**/
    // sort_heap(h.begin(),h.end());
    // printHeap(nodeScore);
    
    return totalSuccess;
}